Information exchange over communication networks is an essential part of the on-going revolution in information technology. In packet switched communication networks, routing of data-blocks or packets at each node is performed based on the information contained in the header of each packet. The networks can be classified into two categories viz., (i) connection-based such as, Asynchronous Transfer Mode (ATM) networks, and (ii) connectionless such as, Internet Protocol (IP) networks.
The IP protocol provides the most flexible, scalable, and robust platform and is currently the most widespread. It is being supported by a variety of applications, including data applications such as, Email, FTP, Web or Internet, as well as digitized voice and video applications. However these applications are typically served on a best-effort basis with no real-time performance guarantees. Since the IP packets are routed individually in a connectionless manner, packets from a given data flow may follow different paths through the network leading to variable performance. Since no network resources are reserved for a given communication channel, the channel performance may vary in terms of throughput, packet delay, delay jitter, and losses. Thus, IP protocol cannot guarantee a quality of service (QoS) in terms of fixed bandwidth, maximum delay, or maximum packet drop-rates.
The tasks performed by IP routers are commonly categorized into two types, routing and forwarding. The execution of routing protocols; creation, maintenance, and updates of routing-tables; exchange of routing information; and signaling are known as the routing tasks. They provide intelligence and decision making capability to configure or modify the data plane, in which the packet forwarding takes place. Thus, the routing tasks are said to constitute the control plane. Whereas, the forwarding tasks constitute the data plane and include receiving the incoming packet, error checking, header extraction, modification, determination of forwarding path, data buffering, scheduling, providing internal switched path, and then, forwarding the packet to the next hop destination. The forwarding tasks are performed on every packet. An IP router is said to perform at wire-speed if it can complete the forwarding tasks on the incoming packets before the arrival of the next ones for minimum size packets at the maximum line speeds (such as OC-48, i.e. 2.5 Gbps for example).
An IP router forwards an IP packet to its destination (or to an intermediate next-hop node in its path) by evaluating its header information. A router first determines a key (or destination IP-address string) from the header of each packet and then performs a look-up in a routing table for the best match with the key. The key may match multiple entries in the look-up table and one entry is chosen based on the best (or the longest prefix) match criterion. The matched entry indicates the output port leading to the next-hop node for the packet towards its final destination. The routing table entries are updated regularly by the routing protocols to reflect the dynamic network conditions. As the routing entries get modified, the forwarding actions on the incoming packets change accordingly.
Packets from a continuing data-stream can be forwarded using a fast, hardware based solution in the router design. In a data flow, once the path for the first packet (or the first few) is established using the routing look-up table then, a requisite entry can be introduced in the fast, hardware based hash-tables. A hashing table consists of a set of compressed, fixed length data entries for keys and the corresponding output ports in a content-addressable memory (CAM) for a quick and reliable parallel search. The ternary CAM (TCAM) chips enable very quick searches of about 10 ns per cycle. However, CAM's are limited in size to a few Mb and cannot store large tables. They are also a lot more expensive than the standard static RAM (SRAM) chips. SRAM chips are also limited in size. Fast dynamic RAM variants, RDRAM and DDRAM chips are also available, which have bigger capacities. In addition to the memory considerations, the common hashing algorithms cannot guarantee the worst-case performance and once the algorithm has to go to second or third choices for large data tables the performance degrades. Any modifications in large hashing tables such as updates, insertions, or removals of entries, are rather complex and slow.
The large look-up tables are typically stored in fast SRAM memory modules in the form of a binary or multi-bit data tries. The trie can be constructed based on the prefix value or the prefix length. The address key of a packet determines the path through the multi-level trie to the final leaf-node. The leaf-node has a pointer to the output port leading to the next-hop destination for the packet. The trie structure is typically optimized to complete the address look-up in two to three memory accesses. Further speed-up can be achieved by implementing the multi-level memory accesses in parallel so as to support one address look-up per memory access cycle.
In a large network the number of entries in a look-up table of a core router can be very large. Traditional A, B, and C type network classes result in IP addresses with fixed prefix lengths of 8, 16, and 24-bits. The introduction of classless network addresses (classless inter-domain routing or CIDR) has led to a greater flexibility in address space allocation by permitting different prefix lengths. However, data sorting schemes that are based on exact matches of fixed length prefixes (8, 16, and 24-bits) are not effective with CIDR. In order to minimize the number of routing table entries, the forwarding paths (or routes) are aggregated using shorter length prefixes, permitting some overlap in address spaces. However, this overlap leads to multiple matches and then the longest prefix match (LPM) has to be selected. The data sorting and look-up scheme has to support the LPM. The migration from IP version-4 addressing system to IP version-6 further complicates the issue, since the IPv6 addresses are 128 bits long instead of 32. The data entries in the look-up table would be correspondingly longer and varied in prefix lengths and diverse in route aggregations.
Currently, a core IP router may have look-up entries in excess of 140,000, which makes the route processing rather slow and costly. Since the look-up tables are very big, an IP router requires a processor with access to a fast (and costly) external memory. Some performance enhancement may be obtained by using different implementation schemes for caching, entry time-out, parallelism, and data structure management. However, the large size of the router look-up table remains a performance bottleneck for high-speed operation and the main reason for high hardware and software costs. It would be useful to make the forwarding decisions very fast and at low cost, thereby reducing or eliminating costs associated with the fast memory storage, access, and data structure management. It is also desirable to simplify the routing tasks of route processing, table updates, and information exchange.
In order to support the real-time voice and video applications connection-based ATM networks are commonly used. In ATM networks end-to-end connections are established as virtual circuits (VCs). The routing decisions for call set-up and tear-down for each data-flow take place in the control-plane, which is kept separate from the data-plane. Each flow consists of fixed-size packets or cells and is identified by its labels or virtual path and circuit identifiers (VPI/VCI). The cell switching takes place in the data-plane by label swapping and forwarding. Once the virtual circuit between a source and destination is established, the data-plane component of ATM switching is fast and at relatively low cost. Thus ATM networks can provide QoS guarantees for real-time applications. However, they do not provide the flexibility and scalability of IP networks and are not suitable for supporting a large number of bursty and short-lived data-flows. In order to support many applications from the IP platform, protocols for mapping IP over ATM are developed.
Multi Protocol Label Switching (MPLS) developed to combine the fast and cheap label swapping technique (from ATM) in the data plane and use IP routing protocols in the control plane. Stand-alone MPLS routers are available, which support a mixed (IP and MPLS) traffic. An existing ATM switch can be modified by adding an adjunct processor running IP routing protocols to make it into a fast and relatively cheap MPLS router with limited capabilities. Conventional IP routing protocols or explicit routing can be used to determine the label-switching paths and to create the forwarding table entries for label swapping. A typical forwarding table may have label bindings of a few hundred to a few thousand. However, a certain fraction of the data-traffic, which does not have an already established label-switched path, follows the conventional IP forwarding. Thus, fast IP forwarding remains an important factor in determining the net performance of an MPLS router and can otherwise act as a bottleneck.
The IP routing tables can be computed using different routing schemes. The common routing protocols can be categorized into two groups, as follows:
(i) Distance-Vector or Path-Vector algorithms: Each router maintains a distance-vector to reach every other known destination node in the network in terms of the minimum number of hops or total cost. Each router forms a consistent picture of the entire network topology and load conditions by exchanging distance-vector (or path-vector) information with its neighbors and modifying its entries accordingly. The information is updated on a regular basis to take into account the dynamic network conditions. Common protocols based on the distance-vector algorithms include Routing Information Protocol (RIP), Border Gateway Protocol (BGP), Exterior Gateway Protocol (EGP), etc.
(ii) Link-State algorithms: Each router broadcasts information about the links directly connected to it to all other routers in the network. Hence, each router has information about the entire network topology and the link costs. The router then computes shortest path (in terms of the minimum number of hops or the least cost) to each destination node by using the Dijkstra algorithm or some other algorithm. Common protocols based on the link-state algorithms include Open Shortest Path First (OSPF) protocol in the Internet and Private Network-Network Interface (PNNI) protocol in ATM networks.
Both the types of algorithms rely on information about the network conditions to flow from distant network nodes to a given router either directly (link-state type) or indirectly (distance-vector type). This requires excessive information storage and exchange leading to excess costs and overhead hits in terms of the available bandwidth, processing speed, hardware costs, memory, and memory I/O. The proposed algorithm would eliminate the necessity for such information exchanges, updates, storage, and all the associated costs. At the same time the network routing would adapt to the dynamic load conditions without any delay. The network can easily mitigate the dynamic situations of link breakages, node outages, or traffic congestions. It would navigate the new and existing communication data streams by bypassing the problem areas.
Typically current networks use routing algorithms that are deterministic and single-path. This can lead to uneven loading in network links and load oscillations under dynamic conditions. Although, multiple-path routing has been studied before, in conventional routing it requires additional information exchange, path computing, routing table space, and complexity. It may be useful to incorporate multi-path and stochastic routing without these additional resources in terms of time, cost, storage, or complexity. This may lead to a fairly even load-balancing in the network and hence, better network utilization and higher throughputs.